package com.wngbms;

import lombok.val;

import java.util.HashSet;
import java.util.Random;

public class LinkListHasLoop {

    public static void main(String[] args) {

//        m1();
//        Node<Integer> head = geneWithLoopLinkList();
        Node<Integer> head = geneWithoutLoopLinkList();
        Node<Integer> fast = head;
        Node<Integer> slow = head;

        boolean f = false;

        while (fast.next != null && fast.next.next != null) {
            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) {
                fast = head;
                f = true;
                break;
            }
        }

        while (f) {
            fast = fast.next;
            slow = slow.next;

            if (fast == slow) {
                System.out.println("has loop n:" + fast.value);
                System.exit(0);
                break;
            }
        }

        System.out.println("no loop");

    }

    private static void m1() {
        //        Node<Integer> head = geneWithoutLoopLinkList();
        Node<Integer> head = geneWithLoopLinkList();
        System.out.println(head);

        Node<Integer> node = head;
        HashSet<Node<Integer>> set = new HashSet<>();

        while (node.next != null) {
            if (set.contains(node)) {
                System.out.println("has loop n: " + node.value);
                System.exit(0);
                break;
            }
            set.add(node);
            node = node.next;
        }

        System.out.println("without loop");
    }

    public static Node<Integer> geneWithLoopLinkList() {
        Integer[] val = new Integer[20];
        Node<Integer> tail = null;
        Node<Integer> pre = null;
        for (int i = 0; i < val.length; i++) {
            Node<Integer> node = new Node<>(pre, val.length - i);
            if (pre == null) {
                tail = node;
            }
            pre = node;
        }

        Random random = new Random();
        int idx = random.nextInt(20);
        System.out.println("idx:" + idx);
        Node<Integer> n = pre;
        for (int i = 0; i < idx; i++) {
            n = n.next;
        }

        System.out.println("loop node: " + n.value);
        tail.next = n;

        return pre;
    }

    public static Node<Integer> geneWithoutLoopLinkList() {
        Integer[] val = new Integer[20];
        Node<Integer> pre = null;
        for (int i = 0; i < val.length; i++) {
            Node<Integer> node = new Node<>(pre, val.length - i);
            pre = node;
        }

        return pre;
    }

    public static class Node<T> {
        Node next;
        T value;

        public Node(Node next, T value) {
            this.next = next;
            this.value = value;
        }
    }


}
